home *** CD-ROM | disk | FTP | other *** search
/ Ian & Stuart's Australian Mac: Not for Sale / Another.not.for.sale (Australia).iso / hold me in your arms / PGP 2.6 / rsaref Toolkit / source / prime.c < prev    next >
C/C++ Source or Header  |  1992-02-29  |  5KB  |  194 lines
  1. /* PRIME.C - primality-testing routines
  2.  */
  3.  
  4. /* Copyright (C) 1991-2 RSA Laboratories, a division of RSA Data
  5.    Security, Inc. All rights reserved.
  6.  */
  7.  
  8. #include "global.h"
  9. #include "rsaref.h"
  10. #include "nn.h"
  11. #include "prime.h"
  12.  
  13. static unsigned int SMALL_PRIMES[] = { 3, 5, 7, 11 };
  14. #define SMALL_PRIME_COUNT 4
  15.  
  16. static int RSAPrime PROTO_LIST
  17.   ((NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));
  18. static int ProbablePrime PROTO_LIST ((NN_DIGIT *, unsigned int));
  19. static int SmallFactor PROTO_LIST ((NN_DIGIT *, unsigned int));
  20. static int FermatTest PROTO_LIST ((NN_DIGIT *, unsigned int));
  21. static int RelativelyPrime PROTO_LIST
  22.   ((NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));
  23.  
  24. /* Find a probable prime a between 3*2^(b-2) and 2^b-1, starting at
  25.    3*2^(b-2) + (c mod 2^(b-2)), such that gcd (a-1, d) = 1.
  26.  
  27.    Lengths: a[cDigits], c[cDigits], d[dDigits].
  28.    Assumes b > 2, b < cDigits * NN_DIGIT_BITS, d is odd,
  29.            cDigits < MAX_NN_DIGITS, dDigits < MAX_NN_DIGITS, and a
  30.            probable prime can be found.
  31.  */
  32. void FindRSAPrime (a, b, c, cDigits, d, dDigits)
  33. NN_DIGIT *a, *c, *d;
  34. unsigned int b, cDigits, dDigits;
  35. {
  36.   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS], v[MAX_NN_DIGITS],
  37.     w[MAX_NN_DIGITS];
  38.   
  39.   /* Compute t = 2^(b-2), u = 3*2^(b-2).
  40.    */
  41.   NN_Assign2Exp (t, b-2, cDigits);
  42.   NN_Assign2Exp (u, b-1, cDigits);
  43.   NN_Add (u, u, t, cDigits);
  44.   
  45.   /* Compute v = 3*2^(b-2) + (c mod 2^(b-2)); add one if even.
  46.    */
  47.   NN_Mod (v, c, cDigits, t, cDigits);
  48.   NN_Add (v, v, u, cDigits);
  49.   if (NN_EVEN (v, cDigits)) {
  50.     NN_ASSIGN_DIGIT (w, 1, cDigits);
  51.     NN_Add (v, v, w, cDigits);
  52.   }
  53.   
  54.   /* Compute w = 2, u = 2^b - 2.
  55.    */
  56.   NN_ASSIGN_DIGIT (w, 2, cDigits);
  57.   NN_Sub (u, u, w, cDigits);
  58.   NN_Add (u, u, t, cDigits);
  59.  
  60.   /* Search to 2^b-1 from starting point, then from 3*2^(b-2)+1.
  61.    */
  62.   while (! RSAPrime (v, cDigits, d, dDigits)) {
  63.     if (NN_Cmp (v, u, cDigits) > 0)
  64.       NN_Sub (v, v, t, cDigits);
  65.     NN_Add (v, v, w, cDigits);
  66.   }
  67.   
  68.   NN_Assign (a, v, cDigits);
  69.   
  70.   /* Zeroize sensitive information.
  71.    */
  72.   R_memset ((POINTER)v, 0, sizeof (v));
  73. }
  74.  
  75. /* Returns nonzero iff a is a probable prime and GCD (a-1, b) = 1.
  76.  
  77.    Lengths: a[aDigits], b[bDigits].
  78.    Assumes aDigits < MAX_NN_DIGITS, bDigits < MAX_NN_DIGITS.
  79.  */
  80. static int RSAPrime (a, aDigits, b, bDigits)
  81. NN_DIGIT *a, *b;
  82. unsigned int aDigits, bDigits;
  83. {
  84.   int status;
  85.   NN_DIGIT aMinus1[MAX_NN_DIGITS], t[MAX_NN_DIGITS];
  86.   
  87.   NN_ASSIGN_DIGIT (t, 1, aDigits);
  88.   NN_Sub (aMinus1, a, t, aDigits);
  89.   
  90.   status = ProbablePrime (a, aDigits) &&
  91.     RelativelyPrime (aMinus1, aDigits, b, bDigits);
  92.  
  93.   /* Zeroize sensitive information.
  94.    */
  95.   R_memset ((POINTER)aMinus1, 0, sizeof (aMinus1));
  96.   
  97.   return (status);
  98. }
  99.  
  100. /* Returns nonzero iff a is a probable prime.
  101.  
  102.    Lengths: a[aDigits].
  103.    Assumes aDigits < MAX_NN_DIGITS.
  104.  */
  105. static int ProbablePrime (a, aDigits)
  106. NN_DIGIT *a;
  107. unsigned int aDigits;
  108. {
  109.   return (! SmallFactor (a, aDigits) && FermatTest (a, aDigits));
  110. }
  111.  
  112. /* Returns nonzero iff a has a prime factor in SMALL_PRIMES.
  113.  
  114.    Lengths: a[aDigits].
  115.    Assumes aDigits < MAX_NN_DIGITS.
  116.  */
  117. static int SmallFactor (a, aDigits)
  118. NN_DIGIT *a;
  119. unsigned int aDigits;
  120. {
  121.   int status;
  122.   NN_DIGIT t[1];
  123.   unsigned int i;
  124.   
  125.   status = 0;
  126.   
  127.   for (i = 0; i < SMALL_PRIME_COUNT; i++) {
  128.     NN_ASSIGN_DIGIT (t, SMALL_PRIMES[i], 1);
  129.     NN_Mod (t, a, aDigits, t, 1);
  130.     if (NN_Zero (t, 1)) {
  131.       status = 1;
  132.       break;
  133.     }
  134.   }
  135.   
  136.   /* Zeroize sensitive information.
  137.    */
  138.   i = 0;
  139.   R_memset ((POINTER)t, 0, sizeof (t));
  140.  
  141.   return (status);
  142. }
  143.  
  144. /* Returns nonzero iff a passes Fermat's test for witness 2.
  145.    (All primes pass the test, and nearly all composites fail.)
  146.      
  147.    Lengths: a[aDigits].
  148.    Assumes aDigits < MAX_NN_DIGITS.
  149.  */
  150. static int FermatTest (a, aDigits)
  151. NN_DIGIT *a;
  152. unsigned int aDigits;
  153. {
  154.   int status;
  155.   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
  156.   
  157.   NN_ASSIGN_DIGIT (t, 2, aDigits);
  158.   NN_ModExp (u, t, a, aDigits, a, aDigits);
  159.   
  160.   status = NN_EQUAL (t, u, aDigits);
  161.   
  162.   /* Zeroize sensitive information.
  163.    */
  164.   R_memset ((POINTER)u, 0, sizeof (u));
  165.   
  166.   return (status);
  167. }
  168.  
  169. /* Returns nonzero iff a and b are relatively prime.
  170.  
  171.    Lengths: a[aDigits], b[bDigits].
  172.    Assumes aDigits >= bDigits, aDigits < MAX_NN_DIGITS.
  173.  */
  174. static int RelativelyPrime (a, aDigits, b, bDigits)
  175. NN_DIGIT *a, *b;
  176. unsigned int aDigits, bDigits;
  177. {
  178.   int status;
  179.   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
  180.   
  181.   NN_AssignZero (t, aDigits);
  182.   NN_Assign (t, b, bDigits);
  183.   NN_Gcd (t, a, t, aDigits);
  184.   NN_ASSIGN_DIGIT (u, 1, aDigits);
  185.  
  186.   status = NN_EQUAL (t, u, aDigits);
  187.   
  188.   /* Zeroize sensitive information.
  189.    */
  190.   R_memset ((POINTER)t, 0, sizeof (t));
  191.   
  192.   return (status);
  193. }
  194.